#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <queue>
#include <utility>

//class Solution {
//public:
//    int m, n;
//    vector<vector<int>> ret;
//    vector<vector<bool>> vis;
//    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
//        m = mat.size();
//        n = mat[0].size();
//        ret.resize(m, vector<int>(n, 0));
//        vis.resize(m, vector<bool>(n, true));
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                ret[i][j] = bfs(mat, i, j);
//            }
//        }
//        return ret;
//    }
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    int bfs(vector<vector<int>>& mat, int i, int j)
//    {
//        if (mat[i][j] == 0)
//            return 0;
//        int ret = 0;
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                vis[i][j] = true;
//            }
//        }
//        queue<pair<int, int>> q;
//        q.push(make_pair(i, j));
//        vis[i][j] = false;
//        while (!q.empty())
//        {
//            int size = q.size();
//            ret++;
//            for (int i = 0; i < size; i++)
//            {
//                //auto [a, b] = q.front();
//                int a = q.front().first;
//                int b = q.front().second;
//                q.pop();
//                for (int j = 0; j < 4; j++)
//                {
//                    int x = a + dx[j];
//                    int y = b + dy[j];
//                    if (x >= 0 && x < m && y >= 0 && y < n && vis[x][y])
//                    {
//                        if (mat[x][y] == 0)
//                            return ret;
//                        vis[x][y] = false;
//                        q.push(make_pair(x, y));
//                    }
//                }
//            }
//        }
//        return 0;
//    }
//};
//
//class Solution {
//public:
//    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
//        int m = mat.size();
//        int n = mat[0].size();
//        vector<vector<int>> ret(m, vector<int>(n, -1));
//        queue<pair<int, int>> q;
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (mat[i][j] == 0)
//                {
//                    ret[i][j] = 0;
//                    q.push(make_pair(i, j));
//                }
//            }
//        }
//        int dx[4] = { 1,-1,0,0 };
//        int dy[4] = { 0,0,1,-1 };
//        while (!q.empty())
//        {
//            auto [a, b] = q.front();
//            q.pop();
//            for (int i = 0; i < 4; i++)
//            {
//                int x = a + dx[i];
//                int y = b + dy[i];
//                if (x >= 0 && x < m && y >= 0 && y < n && ret[x][y] == -1)
//                {
//                    q.push(make_pair(x, y));
//                    ret[x][y] = ret[a][b] + 1;
//                }
//            }
//        }
//        return ret;
//    }
//};


class Solution {
public:
    vector<vector<bool>> vis;
    int m, n;
    int numEnclaves(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        vis.resize(m, vector<bool>(n, true));
        queue<pair<int, int>> q;
        for (int i = 0; i < n; i++)
        {
            if (grid[0][i] == 0)
            {
                vis[0][i] = false;
            }
            else
                q.push(make_pair(0, i));
            if (grid[m - 1][i] == 0)
                vis[m - 1][i] = false;
            else
                q.push(make_pair(m - 1, i));
        }
        for (int i = 1; i < m - 1; i++)
        {
            if (grid[i][0] == 0)
                vis[i][0] = false;
            else
                q.push(make_pair(i, 0));
            if (grid[i][n - 1]==0)
                vis[i][n - 1] = false;
            else
                q.push(make_pair(i, n - 1));
        }
        int dx[4] = { 1,-1,0,0 };
        int dy[4] = { 0,0,1,-1 };
        while (!q.empty())
        {
            //auto [a, b] = q.front();
            int a = q.front().first;
            int b = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = a + dx[i];
                int y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && vis[x][y] && grid[x][y] == 1)
                {
                    vis[x][y] = false;
                    q.push(make_pair(x, y));
                }
            }
        }
        int ret = 0;
        for (int i = 1; i < m - 1; i++)
        {
            for (int j = 1; j < n - 1; j++)
            {
                if (grid[i][j] == 1 && vis[i][j])
                    ret++;
            }
        }
        return ret;
    }
};

class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size();
        int n = isWater[0].size();
        vector<vector<int>> height(m, vector<int>(n, -1));
        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (isWater[i][j] == 1)
                {
                    q.push(make_pair(i, j));
                    height[i][j] = 0;
                }
            }
        }
        int dx[4] = { 1,-1,0,0 };
        int dy[4] = { 0,0,1,-1 };
        while (!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = a + dx[i];
                int y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && height[x][y] == -1)
                {
                    q.push(make_pair(x, y));
                    height[x][y] = height[a][b] + 1;
                }
            }
        }
        return height;
    }
};

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> gap(m, vector<int>(n, -1));
        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1)
                {
                    gap[i][j] = 0;
                    q.push(make_pair(i, j));
                }
            }
        }
        int dx[4] = { 1,-1,0,0 };
        int dy[4] = { 0,0,1,-1 };
        while (!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = a + dx[i];
                int y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && gap[x][y] == -1)
                {
                    gap[x][y] = gap[a][b] + 1;
                    q.push(make_pair(x, y));
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                ret = max(ret, gap[i][j]);
            }
        }
        return ret == 0 ? -1 : ret;

    }
};
int main()
{
    vector<vector<int>> mat = { {0,0,0,0} ,{1,0,1,0},{0,1,1,0},{0,0,0,0} };
   // Solution().updateMatrix(mat);
    Solution().numEnclaves(mat);
    return 0;
}